package codetop.microsoft.T394;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-08-15 10:53:21 星期一
 */
class Solution {
    public String decodeString(String s) {
        Deque<Character> charStack = new LinkedList<>();
        Deque<Integer> numStack = new LinkedList<>();
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int num = 0;
                while (i < s.length()) {
                    char d = s.charAt(i);
                    if (d >= '0' && d <= '9')
                        num = num * 10 + d - '0';
                    else {
                        i--;
                        break;
                    }
                    ++i;
                }
                numStack.push(num);
            } else if (c == ']') {
                int num = numStack.pop();
                StringBuilder sb = new StringBuilder();
                while (!charStack.isEmpty()) {
                    Character d = charStack.pop();
                    if (d == '[')
                        break;
                    else
                        sb.append(d);
                }
                for (int j=0; j<num; ++j) {
                    for (int k=sb.length()-1; k>=0; --k)
                        charStack.push(sb.charAt(k));
                }
            } else
                charStack.push(c);
            ++i;
        }
        StringBuilder sb = new StringBuilder();
        while (!charStack.isEmpty())
            sb.append(charStack.removeLast());
        return sb.toString();
    }
}